package main

// 判断一个连表是否有环, 如果有环则返回连表的环的节点

type ListNode struct {
	Val int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	//	第一步, 判断是否有环
	if head == nil || head.Next == nil {
		return  nil
	}

	slow := head.Next
	fast := head.Next.Next
	hasCycle := false
	for fast != nil && fast.Next != nil {
		if fast == slow {
			hasCycle = true
			break
		}
		slow = slow.Next
		fast = fast.Next.Next
	}

	if !hasCycle {
		// 没有环
		return nil
	}
	// 有环的情况
	fast = head

	for {
		if fast == slow {
			return fast
		}

		fast = fast.Next
		slow = slow.Next
	}
}

func main() {
	
}
